package Exercise;

import java.util.Scanner;

/**
 *   《回文数》
 问题描述
 　　若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
 　　例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。

 　　又如：对于10进制数87：
 　　STEP1：87+78 = 165 STEP2：165+561 = 726
 　　STEP3：726+627 = 1353 STEP4：1353+3531 = 4884

 　　在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

 　　写一个程序，给定一个N（2<=N<=10或N=16）进制数M（其中16进制数字为0-9与A-F），求最少经过几步可以得到回文数。
 　　如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”
 输入格式
 　　两行，N与M
 输出格式
 　　如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否则输出一行”Impossible!”（不含引号）
 */


/** 思路：
 * 思路是把我们不熟悉的进制数转换成熟悉的10进制，在通过相加判断是否为回文数。
 * 进制转换
 * 首先要学会一个进制转换，利用Java的 Long.parseLong(String s, int radix)可以进行转换，
 * s为想要进行转换的进制数，radix为多少进制，得到的是对应转换的10进制数。
 * （当然也有Integer.parseint()的类似方法，用法相同）
 */
public class demo9 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String m = sc.next();
        String str = m;
        int count = 0;
        long sum;
        while (!func(str)){
            count++;
            if(count>30){
                break;
            }
            long num = Long.parseLong(str,n);
            String str1 = "";
            for (int i = str.length()-1; i >=0 ; i--) {
                str1 += String.valueOf(str.charAt(i));
            }
            long num2 = Long.parseLong(str1,n);
            sum = num+num2;
            str = Long.toString(sum,n);
        }
        if(count>30)
        {
            System.out.println("Impossible!");
        }
        else
        {
            System.out.printf("STEP=%d",count);
        }
    }

    public static boolean func(String m){
        boolean b1 = true;
        for (int i = 0; i < m.length()/2; i++) {
            if(m.charAt(i) != m.charAt(m.length()-1-i)){
                b1 = false;
            }
        }
        return b1;
    }
}
